package javatest.algorith;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Stack;

/*
 * N 皇后问题
 */
public class NQueen {
    public int n;

    public static void main(String[] args) {
        // NQueen queen = new NQueen(-1);
        // System.out.println(queen.validCount());
        NQueen queen2 = new NQueen(7);
        System.out.println(queen2.validCount2());
        // int[] a = new int[9];
        
        // for(int i: a){
        //     System.out.println(i);
        // }
        // System.out.println(a.length);
        // a[0] = 10;
        // System.out.println(a.length);
    }
    // TO-DO 位运算解决这个问题

    public NQueen(int n){
        this.n = n;
    }

    public int validCount() {
        
        HashSet<Integer> values = new HashSet<>();
        for(int i=0; i< n; i++){
            values.add(i);
        }
        
        int count = 0;

        for(int i=0; i<n; i++){
            Stack<Integer> record = new Stack<>();
            ArrayList<Integer> nextValues = new ArrayList<>();
            
            record.add(i);
            nextValues.addAll(values);
            nextValues.remove(i);

            count += process(record, nextValues);
        }
        return count;
    }

    public int process(Stack<Integer> record, ArrayList<Integer> nextValues){
        if (record.size() == this.n) {
            // this.printResult(record);
            return 1;
        }
        int count = 0;
        for(int j=0; j<nextValues.size(); j++){
            boolean flag = true;
            for(int i=0; i<record.size(); i++){
                if(record.size() -i == Math.abs(record.get(i) - nextValues.get(j))){
                    flag = false;
                    break;
                }
            }
            if(flag){
                record.add(nextValues.get(j));
                ArrayList<Integer> nextNext = (ArrayList<Integer>) nextValues.clone();
                nextNext.remove(j);
                
                count += process(record, nextNext);
                
                record.pop();
            }
        }

        return count;
    }

    /*
     * 第二种方法
     */
    public int validCount2(){

        int[] record = new int[this.n];
        Arrays.fill(record, -1);
        return process2(0, record);

    }

    public int process2(int rowIndex, int[] record) {
        if(rowIndex == n) return 1;
        int count = 0;
        for(int i=0; i< n; i++){
            if(isValid(rowIndex, i, record)){
                record[rowIndex] = i;
                count += process2(rowIndex+1, record);
            }
        }
        record[rowIndex] = -1;
        return count;
    }
    public boolean isValid(int rowIndex, int colIndex, int[] record){
        for(int j=0; j<rowIndex; j++){
            if(record[j] == colIndex) return false;
            if((rowIndex-j) == Math.abs(colIndex-record[j])) return false;
        }
        return true;
    }
    public void printResult(Collection<Integer> record){
        int n = record.size();
        for(Integer index: record){
            for(int i=0; i<n; i++){
                if (i != index) System.out.print(0 + " ");
                else System.out.print(1 + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
